package tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ConstructBinaryTreeFromInorderAndPostorderTraversal106 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {

        if (postorder.length < 1 || inorder.length < 1) {
            return new TreeNode();
        }
        return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }


    private TreeNode buildTree(int[] in, int in_begin, int in_end,
                               int[] postorder, int postorder_begin, int postorder_end) {
        if (postorder_begin > postorder_end) {
            return null;
        }

        if (in_begin > in_end) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postorder_end]);
        int index = in_end;
        for (int i = in_end; i >= in_begin ; i--) {
            if (in[i] == root.val) {
                index = i;
                break;
            }
        }
        root.left = buildTree(in,in_begin, index-1,
                postorder, postorder_begin, postorder_begin+(index-in_begin)-1);
        root.right = buildTree(in, index+1, in_end,
                postorder, postorder_begin+(index-in_begin), postorder_end-1);

        return root;

    }



}
